package com.chj.jz.dp.class04;

public class Code03_CopyBooks {
	/**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    public static int copyBooks(int[] pages, int k) {
        // write your code here
    	
    	int n = pages.length;
    	if(n == 0) {
    		return 0;
    	}
    	
    	if(k > n) {
    		k = n;
    	}
    	
    	int[][] f = new int[k + 1][n + 1];
    	int i, j, kk;
    	f[0][0] = 0;
    	for(i = 1; i <= n; i++) {
    		f[0][i] = Integer.MAX_VALUE;
    	}
    	
    	for(kk = 1; kk <= k; kk++) {
    		f[kk][0] = 0;
    		
    		for(i = 1; i <= n; i++) {
    			f[kk][i] = Integer.MAX_VALUE;
    			
    			int sum = 0;
    			for(j = i; j >= 0; j--) {
    				f[kk][i] = Math.min(f[kk][i], Math.max(f[kk - 1][j], sum));
    				if(j > 0) {
    					sum += pages[j - 1];
    				}
    			}
    		}
    	}
    	
    	return f[k][n];
    }
    
    public static void main(String[] args) {
		{
			int[] arr = new int[] {3, 2, 4};
			int k = 2;
			System.out.println(copyBooks(arr, k));
		}
		{
			int[] arr = new int[] {3, 2, 4};
			int k = 3;
			System.out.println(copyBooks(arr, k));
		}
    }
}
